//
//  Backtracking.swift
//  ArithmeticClass15
//
//  Created by xiangzuhua on 2021/1/29.
//

class Backtracking {
    // MARK:- 八皇后
    // 存储八皇后，下标为行，值为列
    static var eightQueues: [Int] = [Int](repeating: -1, count: 8)
    // 实现八皇后的摆法数
    static var count = 0
    class func cal8Queues(_ row: Int) {
        if row == 8 {
            // 打印八皇后的位置
            printQueues()
            count += 1
            print(count);
            return
        }
        for colum in 0..<8 {// 每一行都有八种方法
            if isQueue(row, colum: colum) {// 满足要求，存储皇后
                eightQueues[row] = colum
                cal8Queues(row + 1)// 继续考察下一行
            }
        }
    }
    
    class func isQueue(_ row: Int, colum: Int) -> Bool {
        if row == 0 {
            return true
        }
        
        var leftup = colum - 1
        var rightup = colum + 1
        for i in (0...row-1).reversed() {
            // 竖向对比
            if eightQueues[i] == colum{
                return false
            }
            // -45度对角线
            if leftup >= 0 &&  eightQueues[i] == leftup {
                return false
            }
            // +45度对角线
            if rightup < 8 && eightQueues[i] == rightup {
                return false
            }
            
            leftup -= 1
            rightup += 1
        }
        return true
    }
    
    class func printQueues() {
        for i in 0..<8 {
            var temp = ""
            for j in 0..<8 {
                if eightQueues[i] == j{
                    temp += "Q"
                } else {
                    temp += "*"
                }
            }
            print(temp)
        }
    }
    
    //MARK:- 0-1背包问题
    static var maxWeight = Int.min
    class func backpack0_1(whitchOne i: Int, currentWeight: Int, items: [Int], count: Int, capacity: Int) {
        if currentWeight == capacity || i == count {
            if currentWeight > maxWeight {
                maxWeight = currentWeight
            }
            return
        }
        
        backpack0_1(whitchOne: i + 1, currentWeight: currentWeight, items: items, count: count, capacity: capacity)
        if items[i] + currentWeight < capacity {
            backpack0_1(whitchOne: i + 1, currentWeight: items[i] + currentWeight, items: items, count: count, capacity: capacity)
        }
    }
    
    // 正则表达式
    var regularExpression: [Character]
    var expressionLength: Int
    var match:Bool = false
    init(regular expression:[Character], exprLength: Int) {
        regularExpression = expression
        expressionLength = exprLength
    }
    
    func match(_ text: [Character], length: Int) -> Bool {
        match = false
        rmatch(0, regular: 0, chars: text, length: length)
        return match
    }
    
    func rmatch(_ textIndex: Int, regular expressionIndex: Int, chars: [Character], length: Int)  {
        if match {// 已经匹配不需要继续递归
            return
        }
        
        if expressionIndex == expressionLength {// 正则表达式到达末尾
            if textIndex == length {// 字符串匹配到了末尾
                match = true
            }
            return
        }
        
        if regularExpression[expressionIndex] == Character("*") {// * 匹配任意多个字符
            // 因为*可以匹配多个字符，所以有length - textIndex种情况，即字符串textIndex下标及后面的字符都有可能要与*号匹配上
            for k in 0..<length - textIndex {
                rmatch(textIndex + k, regular: expressionIndex + 1, chars: chars, length: length)
            }
        } else if regularExpression[expressionIndex] == Character("?"){// ?号匹配0个或者1个字符
            // 字符串中当前位置的字符与正则表达式 ? 后面的字符匹配
            rmatch(textIndex, regular: expressionIndex + 1, chars: chars, length: length)
            
            // 字符串中下一个字符与 ? 后面的字符匹配
            rmatch(textIndex + 1, regular: expressionIndex + 1, chars: chars, length: length)
        } else if(textIndex < length && regularExpression[expressionIndex] == chars[textIndex]){// 纯字符串匹配
            rmatch(textIndex + 1, regular: expressionIndex + 1, chars: chars, length: length)
        }
        
        
    }
    
    
}
